
#include <dirent.h>
#include <string.h>
#include "config.h"
#include "choose.h"
#include "filter.h"
#include "blacklist.h"
#include "random.h"
#include <assert.h>

/*

You can prove by mathematical induction that this algorithm 
will always pick one of the songs that passes the filters, 
and will pick each such song with the same probability.
Assuming that the random number generator is unbiased. 

Given:
random_range (count) is uniformly distributed in (0, count]. 

Base case: When there is only one song, 
count = 1, so random_range (count) = 0.
We thus choose that song with probability 
  1
----- = 1
count

Hypothesis: If we have seen k songs, and the probabilty of 
choosing each of them is 
1
-
k
and we now look at the (k + 1)th song, we will choose that song
with probability 
  1
-----
k + 1
and we will not choose it with probability 
  k
-----
k + 1

The probability that any of the previous k songs is chosen is now 
1     k       1
- * ----- = -----. Q E D.
k   k + 1   k + 1
*/

void choose (char const * const directory, char * const filename)
{
	DIR *musicdir;
	struct dirent *entry;
	musicdir = opendir(directory);
	uint32_t count = 0;
	uint32_t random;

	while ((entry = readdir(musicdir)))
	{
		if ((filter (entry->d_name)))
		{	
			count = count + 1;
			random = random_range (count);
			assert (random < count);
			if (random == 0)
			{
				strncpy (filename, directory, 256);
				strncat (filename, entry->d_name, 256);
			}
		}
	}
	/*
	 * The song that was chosen this time won't be chosen again
	 * until the blacklist forgets about it.
	 */
	update_blacklist (count);
	insert_blacklist (filename);
	closedir (musicdir);
}

